package top.ddltech.algorithm.sort;

import top.ddltech.algorithm.util.SortUtil;

/**
 * 插入排序
 */
public class InsertionSort {

    /**
     * 将a[]按升序排列
     *
     * @param a 数组
     */
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            // 将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
            Comparable tmp = a[i];
            int j = i;
            for (; j > 0 && SortUtil.less(tmp, a[j - 1]); j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }
}
